Ëàáîðàòîðíàÿ ðàáîòà ¹ 1.

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА

Факультет управления

Кафедра «Моделирование в экономике и управлении»

А.Г. МАДЕРА

Курс

МАТЕМАТИЧЕСКИЕ МОДЕЛИ В УПРАВЛЕНИИ

Методическое пособие по проведению лабораторных работ

по теме “Линейное программирование”

Лабораторная работа №2

Транспортные задачи и их решение средствами Excel

Москва 2004

Введение

Курс “Математические модели в управлении” читается студентам второго курсов дневной и вечерней форм обучения факультета управления по специальностям: 061000 – "Государственное и муниципальное управление", 061100 – "Менеджмент". Курс читается два семестра и охватывает основные темы исследования операций, теории массового обслуживания и теории игр.

Предметом изучения дисциплины “Математические модели в управлении” являются математические модели и методы решения исследования операций, теории массового обслуживания и теории игр.

Цель курса - сформировать у студентов комплекс знаний необходимых для:

· анализа современных проблем в области производства, торговли, финансов, денежного обращения и кредитов;

· оптимальному решению тактических и стратегических задач организационного управления;

Задачи курса научить студентов:

· владеть приемами постановки задач организационного управления;

· на основе описательных задач строить математические модели;

· умению выбрать соответствующий метод решения задачи;

· проведению численных исследований математических моделей;

· умению проведения анализа результатов вычислений;

· умению выбрать наиболее эффективное управляющее решение.

Особенностью программы для студентов факультета управления является:

· рассмотрение актуальных проблем организационного управления в различных структурах – производственных, торговых, финансово – кредитных;

· применение математических методов при анализе и выработки управляющих решений.

Изучив курс, студент:

должен владеть моделями математического программирования, теории игр и массового обслуживания;

уметь использовать математические методы при решении задач организационного управления;

должен уметь использовать в своей работе средства вычислительной техники и современных информационных технологий.

Лабораторные работы призваны, на практике, помочь студентам применить знания полученные на лекциях и при самостоятельной работе. В качестве программной среды используются средства Microsoft Offis Excel (электронные таблицы MS Offis).

Программные средства Excel - Поиск решения является мощным инструментом решения оптимизационных задач. С их помощью можно найти наилучший вариант использования ограниченных ресурсов, обеспечивающий максимальное значение для одних величин, например, прибыли, или же минимальное - для других, например, затрат.

Использования поиска решения поможет дать ответ на такие вопросы:

· Какая цена или ассортимент товаров обеспечат максимальную прибыль?

· Как не выйти за пределы бюджета?

Порядок выполнения работы

На лабораторную работу каждый студент приносит чистую, неиспользованную дискету МД 3,5'. На этой дискете будут содержаться файлы с исходными данными и результатами по всем выполненным работам.

Задание. Получить вариант задачи у преподавателя. Составить математическую модель задачи. Найти оптимальное решение задачи в Excel и показать результаты поиска решения преподавателю на экране компьютера. Отчет составляет на МД.

Отчет. Отчет по лабораторной работе представляется на дискете студента и должен содержать файл с названием ЛР 2 Вариант №… Отчет (Фамилия № группы).

Состав отчета, записанный на МД:

- математическая модель задачи, предъявляемая преподавателю (может быть написана от руки).

- Рабочий лист Excel с исходными данными и математической моделью, протокол решения задачи, куда входят:

- результаты решения в виде отчета Результаты

Отчет на компьютере и МД демонстрируется преподавателю на данном лабораторном занятии.

Сдача лабораторной работы преподавателю принимается только при наличии у студента МД с результатами расчета и отметки у преподавателя о выполненной лабораторной работе. Во время сдачи лабораторной работы студент должен уметь проводить анализ полученных результатов.

Лабораторная работа № 2.

Тема: Транспортные задачи и их решение средствами Excel.

Программное обеспечение: Microsoft Excel

Основные сведения

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁, А₂, …, А_m в n пунктов назначения В₁, В₂, …, В_n . При этом в качеств критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим c_ij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через a_i – запасы груза в i-ом пункте отправления, через b_j – потребности в грузе в j-ом пункте назначения, а через x_ij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка зачади состоит в определении минимального значения функции

(1)

при условиях

(2)

(3)

(4)

Поскольку переменные удовлетворяют системам линейных уравнений (2) и (3) и условию неотрицательности (4), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

= , (5)

то модель такой транспортной задачи называется закрытой. В противном случае – открытой.

В случае превышения запаса над потребностью, т.е.

вводится фиктивный (n+1) потребитель (или пункт назначения) с потребностью равной b_n₊₁ = – , а соответствующие транспортные тарифы от всех поставщиков до фиктивного потребителя полагаются равными нулю. Полученная задача становится закрытой транспортной задачей, для которой выполняется равенство (5).

В случае превышения потребности некоторого потребителя над общими запасами, т.е.

вводится фиктивный (m+1) пункт отправления с запасом груза в нем, равным с потребностью равной a_m₊₁ = – , а соответствующие транспортные тарифы от фиктивного поставщика до всех потребителей полагаются равными нулю. Полученная задача становится закрытой транспортной задачей, для которой выполняется равенство (5).

Рассмотрим конкретную задачу:

Задача. Четыре предприятия данного экономического района для производства продукции получают сырье от трех поставщиков. Потребности в сырье каждого из предприятий соответственно равны 900, 600, 800 и 600 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 600, 800 и 1000 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Построение математической модели

Обозначим через x_ij количество единиц сырья, перевозимого из i-го пункта его получения на j-е предприятие. Задача является открытой, так как сумма запасов грузов 600 + 800 + 1000 = 2400 в местах отправления, не равна сумме потребностей грузов в местах назначения 900 + 600 + 800 + 600 = 2900. Так как потребности в грузах превышают их запасы, то вводим фиктивного поставщика с номером 4, у которого запас груза равен 2900 – 2400 = 500. В этом случае общий запас станет равным 2900 и мы получим закрытую транспортную задачу. При этом все тарифы от фиктивного поставщика ко всем потребителям груза полагаются равными нулю. В матрице тарифов появится четвертая строка, в которой стоят все нули. Целевая функция не изменится.

Условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

x₁₁ + x₁₂ + x₁₃.+ x₁₄.= 600 (6)

x₂₁ + x₂₂ + x₂₃.+ x₂₄.= 800 (7)

x₃₁ + x₃₂ + x₃₃.+ x₃₄.= 1000 (8)

x₄₁ + x₄₂ + x₄₃.+ x₄₄.= 500 (9)

x₁₁ + x₂₁ + x₃₁. + x₄₁ = 900 (10)

x₁₂ + x₂₂ + x₃₂..+ x₄₂= 600 (11)

x₁₃ + x₂₃ + x₃₃. + x₄₃= 800 (12)

x₁₄ + x₂₄ + x₃₄. + x₄₄= 600 (13)

При данном плане перевозок , общая стоимость перевозок составит

F = 4x₁₁ + 3x₁₂ + 2₁₃.+ 1x₁₄ + 2x₂₁ + 1x₂₂.+ 7x₂₃ +

+ 9x₂₄ + 3x₃₁ + 6x₃₂.+ + 8x₃₃ + 4x₃₄ → min. (14)

Таким образом, математическая постановка задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (6)–(13), при котором целевая функция (14) принимает минимальное значение.

Решение задачи средствами Microsoft Excel

Подпись:
Рис. 1. Фрагмент Листа рабочей книги с исходными данными
Вызовите Microsoft Excel. В новой рабочей книге переименуйте "Лист№1" в ЛР 2 Вариант №… Отчет (Фамилия № группы)

Задание Исходных данных задачи

Начиная с ячейки с именем А1 на Листе окна Excel постройте следующую таблицу (рис. 1.):

Ячейки с адресами В4:Е7 резервируются для переменных (рис. 1) – это изменяемые ячейки. В ячейках F4:F7 заносятся запасы грузов в пунктах отправления, включая и

фиктивный, в ячейках B9:E9 заносятся потребности (спрос) в грузах в пунктах назначения.

После занесения в ячейку числа или формулы необходимо нажать клавишу ENTER.

В ячейки с адресами В15:Е18 занесены коэффициенты матрицы затрат на перевозку грузов.

Ячейки G4:G7 содержат формулы для расчета ограничений (6) – (9). Формула ограничения (6) занесена в ячейку G4 и имеет вид =СУММ(B4:E4). Соответственно ограничения (7), (8) и (9) занесены в ячейки G5, G6 и G7 в виде формул =СУММ(B5:E5), =СУММ(B6:E6) и =СУММ(B7:E7).

В ячейках В10:Е10 содержатся формулы ограничений (9)–(12), которые соответственно имеют вид: =СУММ(B4:B7), =СУММ(C4:C7), =СУММ(D4:D7), =СУММ(E4:E7).

В ячейки В15:Е18 занесены матрица затрат на перевозки между всеми пунктами отправления груза и назначения. Четвертая строка этой матрицы соответствует перевозкам от фиктивного поставщика.

Формула для расчета Целевой функции (13) занесена в ячейку С19 и имеет вид: =СУММПРОИЗВ(B15:E18;B4:E7). В эту же ячейку будет занесено вычисленное значение целевой функции.

Подпись:
Рис. 2. Диалоговое окно Поиск решения с занесенными формулами ограничений

Решение задачи

Поставить курсор мыши в ячейку С19, в которой будет содержаться вычисленное значение целевой функции, и нажать на левую кнопку мыши.

Войти в меню Сервис, выбрать в нем Поиск решения и щелкнуть на нем левой кнопкой мыши. На экране появится диалоговое окно Поиск решения (рис. 2).

Подпись: Рис. 3. Диалоговое окно Добавление ограничения

Подпись:
Рис. 4. Диалоговое окно Параметры поиска решения
В поле Установить целевую ячейку заносится $С$19. Для этого проще всего установить курсор мыши внутрь ячейки, щелкнуть в ней левой кнопкой мыши, затем щелкнуть мышью на ячейке С17.

Поскольку ищется минимум целевой функции, то после слова Равной выделим Минимальному значению, щелкнув в кружочке мышью.

В поле Изменяя ячейки занесем диапазон $B$4:$Е$7 так как именно эти ячейки отведены под значения вычисляемых переменных. Для этого поставим курсор в поле Изменяя ячейки , затем поставим курсор на ячейке В4 и при нажатой левой кнопке мыши переведем курсор на ячейку Е7. В поле Изменяя ячейки появится необходимый диапазон ячеек.

В поле Ограничения занесем ограничения (6)–(12), (14), а также условия неотрицательности переменных. Для этого щелкнем мышью на кнопке Добавить. Появится диалоговое окно Добавление ограничения (рис. 3). Третье ограничение (рис. 2) занесено следующим образом: в окне Поиск решения щелкнуть на кнопке Добавить. Откроется диалоговое окно Добавление ограничения. В поле Ссылка на ячейку поставить курсор мыши нажать на левую ее кнопку. Затем поставить курсор мыши на ячейку G4, глее введено ограничение и при нажатой кнопке мыши провести вплоть до ячейки с адресом G7. В среднем поле окна Добавить ограничения выбираем знак равенства, а в последнем поле описанным выше способом заносим ячейки F4:F7, содержащие запасы поставщиков. Аналогично заносятся и другие ограничения (рис. 2).

Снова в поле Поиск решения (рис. 2). Щелкнуть мышью на кнопке Параметры.

На экране появится диалоговое окно Параметры поиска решения. В этом окне (рис. 4) устанавливаются параметры поиска решения. Здесь отметить квадратики Линейная модель, Неотрицательные значения, Автоматическое масштабирование. Щелкнем на кнопке ОК.

Подпись:
Рис. 5. Диалоговое окно Результаты поиска решения

Снова попадаем в диалоговое окно Поиск решения. В этом окне (рис. 2) щелкнем левой кнопкой мыши на кнопку Выполнить. На экран выводится окно Результаты поиска решения (рис. 5).

Одновременно на Листе экрана также появляются результаты решения задачи (рис. 6): в столбце и строке Ограничения выводятся их рассчитанные значения . В ячейках В4:Е7 содержатся значения рассчитанных переменных – объемов перевозок от каждого пункта отправления к каждому пункту назначения. В ячейке с целевой функцией С19 – рассчитанное значение целевой функции.

Итак найдено решение: F_min = 5200, x₁₁ = 0, x₁₂ = 0, x₁₃.= 300, x₁₄ = 300, x₂₁ = 200, x₂₂.= 600, x₂₃ = 0, x₂₄ =0, x₃₁ = 700, x₃₂.= 0, x₃₃ = 0, x₃₄.= 300, и фиктивные переменные x₄₁ = x₄₂ =+x₄₄.= 0, x₄₃.= 500.

Подпись:
Рис. 6. Результаты решения транспортной задачи в окне Excel

Замечание. Прежде чем приступать к решению транспортной задачи данного варианта, необходимо проверить баланс между общим запасом груза у поставщиков и общей потребностью у потребителей. Если соответствующие суммы не равны между собой, необходимо ввести либо фиктивного поставщика, либо фиктивного потребителя (см. выше).

Индивидуальные задания:

Вариант № 1.

Необходимо решить транспортную задачу: минимизировать расходы на доставку продукции заказчикам со складов фирмы, учитывая следующие затраты на доставку одной единицы продукции, объём заказа и количество продукции, хранящейся на каждом складе. Тарифы на перевозку единицы продукции, объёмы запасов продукции на складах, а также объёмы заказанной продукции представлены в таблице №1.

Склад	Магазины заказчики					Запасы на складе (ед. прод)
	“Анна”	“Вада”	“Ева”	“Алла”	“Мех”
“Таганка”	1	3	4	5	2	20
“ВВЦ”	2	1	1	4	5	15
“Щёлково”	1	3	3	2	1	40
“Коньково”	3	1	4	2	3	15
Объём заказа (ед. прод)	15	10	25	5	9